﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdbool.h>


//给你两个字符串 haystack 和needle
//请你在haystack字符串中找出needle字符串的第一个匹配项的下标(下标从0开始)
//如果needle不是haystack的一部分,则返回 -1 

int strStr(char* haystack, char* needle)
{
    int i, j = 0;
    for (i = 0; i < strlen(haystack); i++)
    {
        if (haystack[i] == needle[j]) 
        {
            j++;
        }
        else
        { 
            i = i - j;
            j = 0;
        }
        if (j == strlen(needle)) 
        {
            return i - j + 1;
        }
    }
    return -1;
}







//自己的方法(时间复杂度可能会高一点)，上面那个for循环可以通过LeetCode

int strStr(char* haystack, char* needle)
{
    char* a = NULL;
    char* b = NULL;
    int i = 0;
    while (haystack)
    {
        a = haystack;
        b = needle;
        while (*a == *b && *a)
        {
            a++;
            b++;
            if (*b == '\0')
            {
                return i;
            }
        }
        if (!*a)
        {
            return -1;
        }
        haystack++;
        i++;
    }
    return 0;
}


int main()
{
    char haystack[] = "abcdedefg";
    char needle[] = "efg";
    int ret=strStr(haystack, needle);
    printf("%d ", ret);
}

















//错误
//
//bool sanagram(char* s, char* t)
//{
//    int i = 0;
//    int a = 0;
//    int b = 0;
//    for (i = 0; i < strlen(s); i++)
//    {
//        a += (int)s[i];
//        b += (int)t[i];
//    }
//    if (a == b)
//    {
//        return true;
//    }
//    return false;
//}
//
//
//
//
//错误
//
//bool sanagram(char* s, char* t)
//{
//    int i = 0;
//    int a = 0;
//    int b = 0;
//    for (i = 0; i < strlen(s); i++)
//    {
//        a += (int)s[i];
//    }
//    for (i = 0; i < strlen(t); i++)
//    {
//        b += (int)t[i];
//    }
//
//    if (a == b)
//    {
//        return true;
//    }
//    else
//    {
//        return false;
//    }
//}









//哈希表做法，将字母减去'a'变成普通数字，然后把对应的数字的下标++或--，
//因为++和--可以抵消，所以一旦有--没有抵消的，下标就变成-1了，
//说明另一个字符串里面没有这个字母，因为要是有的话会++，就不会变成-1了
//所以一旦--变成-1就返回false

bool sanagram(char* s, char* t)
{
    int len_s = strlen(s), len_t = strlen(t);
    if (len_s != len_t) 
    {
        return false;
    }

    int table[26];
    memset(table, 0, sizeof(table));

    for (int i = 0; i < len_t; ++i) 
    {
        table[t[i] - 'a']++;
    }
    for (int i = 0; i < len_s; ++i)
    {
        table[s[i] - 'a']--;

        if (table[s[i] - 'a'] < 0)
        {
            return false;
        }
    }
    return true;

}

int main()
{
    char s[] = "acbb";
    char t[] = "bbca";
    int a=sanagram(s, t);
    printf("%d", a);
    return 0;
}